package com.zac.coroutine.algorithm.leetcode.array

import com.zac.coroutine.algorithm.leetcode.TestUtils.print

/**
 * author zac
 * date 2025/8/6
 *338. 比特位计数
 * 给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。
 */
object CountBits {
    @JvmStatic
    fun main(args: Array<String>) {
        countBits(5).print()
    }

    fun countBits(n: Int): IntArray {
        val arr = IntArray(n + 1)

        for (i in 0 until n + 1) {
            var x = i
            var sum = 0
            while (x != 0) {
                sum += if (x % 2 == 1) 1 else 0
                x = x / 2
            }
            arr[i] = sum
        }
        return arr
    }

    /**
     *
     * 涉及到二进制的算法,很可能会用到位运算
     * 官方题解:1.Brian Kernighan 算法
     * Brian Kernighan 算法的原理是：对于任意整数 x，令 x=x & (x−1)，该运算将 x 的二进制表示的最后一个 1 变成 0。
     * 因此，对 x 重复该操作，直到 x 变成 0，则操作次数即为 x 的「一比特数」。
     */
    fun countBits1(n: Int): IntArray {
        val arr = IntArray(n + 1)
        for (i in 0 until n + 1) {
            var x = i
            var time = 0
            while (x > 0) {
                x = x and (x - 1)
                time++
            }
            arr[i] = time
        }
        return arr


    }

    /**
     * 对于后面的结果与前面的结果存在某种相关的
     * 比如
     * 斐波那契数列 1,1,2,3,5,8
     * 这种
     * 要直接想到动态规划来缩短时间复杂度
     */
   /* fun countBits2(n: Int): IntArray {

    }*/


    }